The physical storage mechanism in memory fundamentally determines the performance characteristics of arrays and linked lists.
- We just established that pointers enable nodes to locate one another using explicit memory addresses. This fundamental mechanism dictates the key difference in how arrays and linked lists are physically stored in system memory.
- The distinction between logical order (the sequence we define) and physical order (where data lives in RAM) is crucial for understanding performance trade-offs, particularly for insertion and access:
- Arrays (Physical Contiguity): Elements are stored in a single, contiguous block of memory.
- Calculating the address of the element at index $i$ is trivial: $\text{Address}(i) = \text{Base\_Address} + i \times \text{Element\_Size}$. This guarantees instantaneous, random access in $O(1)$ time.
- Linked Lists (Physical Scatter): Nodes (using the Node_Structure) are allocated dynamically and can be scattered across disparate locations in memory.
- The logical sequence is maintained solely by the explicit pointers stored in the `next` field.
- Accessing the $i$-th element requires sequential traversal (following the links), resulting in $O(n)$ access time.
Memory Layout and Access Comparison
| Structure | Memory Layout | Access Time (Index $i$) |
|---|---|---|
| Array | Contiguous Block | $O(1)$ |
| Linked List | Scattered/Dynamic | $O(n)$ |
The $O(1)$ access for arrays is due to cache locality, which is lost when nodes are scattered across memory.